1. Technical Field
The present invention relates in general to a method and system for managing memory devices and in particular to a method and system for providing enhanced queueing efficiency within a data storage device. More particularly, the present invention relates to an improved memory linking method and system whereby storage block addresses and data objects are strategically associated, such that the number of system cycles required to enqueue or dequeue to or from a data storage system is reduced.
2. Description of the Related Art
A xe2x80x9clinked listxe2x80x9d is known in both the hardware memory and software arts as a chain of items which each point to the next item in the linked list in a sequential manner. Such a list of elements or nodes comprise an ordered data structure which is held together by the use of pointers. Within this context, a xe2x80x9cpointerxe2x80x9d is a variable that comprises the memory location (memory address) of the data block to which it points in sequence. A singly linked list is comprised of data blocks which include a single pointer to the next sequential block. Each of the data blocks in a double linked list includes two pointersxe2x80x94one pointing to the following block and the other pointing to the preceding block. In a circular-linked list, the last data block points to the first data block.
Referring to FIG. 1, there is depicted a conventional memory management system 100. As seen in FIG. 1, memory management system 100 includes a linked list 105 having serially linked storage blocks 108, 110, and 112. In this three-block linked list, storage block 108 is the first storage block (hereinafter referred to as the xe2x80x9cheadxe2x80x9d) within the series, and storage block 112 is the last storage block (hereinafter referred to as the xe2x80x9ctailxe2x80x9d).
Memory management system 100 further includes a head register 102, a tail register 104, and a count register 106 which function as boundary and parametric guides for linked list 105. Head register 102 tracks head block 108 from which data objects within linked list 105 are dequeued. Count register 106 maintains a count of the number of storage blocks within linked list 105. This count is updated for each enqueueing or dequeueing operation performed by memory management system 100. Tail register 104 tracks tail block 112 prior to a conventional data enqueue operation such as that described as follows.
A typical enqueueing process is initiated by a request to memory management system 100 to add a data object 126 to linked list 105. In response to the data enqueue request, the address of tail block 112 is read from tail register 104. An address register (not depicted) for free pool 130 is then accessed to obtain the address of an available storage block 114 within free pool 130. The address of storage block 114 will become a new tail pointer 121 which is written into pointer field 120 of old tail block 112. A second write operation is then required to write data object 126 into the data field of new tail block 114. A data enqueueing operation within memory management system 100 thus requires accessing and writing to two physically separate memory locations which is costly in terms of processing overhead.
It would therefore be desirable to provide a method and system for reducing the number of processing cycles required to queue data to or from a linked list data storage device.
A method and system are disclosed for queueing data within a data storage device including a set of storage blocks each having an address, a pointer field, and a data field. This set of storage blocks comprises a linked list of associated storage blocks and also a free pool of available storage blocks. The storage device further includes a tail register for tracking an empty tail block from which a data object is enqueued into the linked list. A request to enqueue a data object into the linked list is received within the data storage system. In response to the data enqueue request, an available storage block from the free pool is selected and associated with the tail register. A single write operation is then required to write the data object into the data field of a current tail block and to write the address of the selected storage block into the pointer field of the current tail block, such that the selected storage block becomes a new tail block to which the tail register points.